<p id="f-6-map-md"></p>
<h1>Maps</h1>

<p>In Go, the capacity of a map is unlimited in theory, it is only limited by available memory.
That is why the built-in <code>cap</code> function doesn't apply to maps.</p>

<p>In the official standard Go runtime implementation, maps are implemented as hashtables internally.
Each map/hashtable maintains a backing array to store map entries (key-value pairs).
Along with more and more entries are put into a map,
the size of the backing array might be thought as too small to store more entries,
thus a new larger backing array will be allocated
and the current entries (in the old backing array) will be moved to it,
then the old backing array will be discarded.</p>

<p>In the official standard Go runtime implementation, the backing array of a map will never shrink,
even if all entries are deleted from the map. This is a form of memory wasting.
But in practice, this is seldom a problem and and actually often good for program performances.</p>

<h2>Clear map entries</h2>

<p>We could use the following loop to clear all entries in a map:</p>

<pre><code class="language-Go">	for key := range aMap {
		delete(aMap, key)
	}
</code></pre>

<p>The loop is specially optimized (except entries with NaN keys exist) so that its execution is very fast.
However, please note that, as mentioned above, the backing array of the cleared map doesn't shrink after the loop.
Then how to release the backing array of the map? There are two ways:</p>

<pre><code class="language-Go">	aMap = nil
	// or
	aMap = make(map[K]V)
</code></pre>

<p>If the backing array of the map is not referenced elsewhere, then the backing array will be collected eventually after being released.</p>

<p>If there will be many new entries to be put in the map after it is cleared, then the former way is preferred;
otherwise, the latter (release) ways are preferred.</p>

<p>Since Go 1.21, there is a better way to do this job.
Go 1.21 introduced a new built-in function, <code>clear</code>, which may be used to clear all entries in a map,
including those ones with NaN keys.</p>

<p>Note: currently (Go toolchain 1.24), using the built-in <code>clear</code> function to
clear a map with at least one entry takes time proportional to the size of the backing array of the map.</p>

<h2><code>aMap[key]++</code> is more efficient than <code>aMap[key] = aMap[key] + 1</code></h2>

<p>In the statement <code>aMap[key] = aMap[key] + 1</code>, the <code>key</code> are hashed twice,
but in the statement <code>aMap[key]++</code>, it is only hashed once.</p>

<p>Similarly, <code>aMap[key] += value</code> is more efficient than <code>aMap[key] = aMap[key] + value</code>.</p>

<p>These could be proved by the following benchmark code:</p>

<pre><code class="language-Go">package maps

import &quot;testing&quot;

var m = map[int]int{}

func Benchmark_increment(b *testing.B) {
	for i := 0; i &lt; b.N; i++ {
		m[99]++
	}
}

func Benchmark_plusone(b *testing.B) {
	for i := 0; i &lt; b.N; i++ {
		m[99] += 1
	}
}

func Benchmark_addition(b *testing.B) {
	for i := 0; i &lt; b.N; i++ {
		m[99] = m[99] + 1
	}
}
</code></pre>

<p>The benchmark results:</p>

<pre><code>Benchmark_increment-4  11.31 ns/op
Benchmark_plusone-4    11.21 ns/op
Benchmark_addition-4   16.10 ns/op	
</code></pre>

<h2>Pointers in maps</h2>

<p>If the key type and element type of a map both don't contain pointers,
then in the scan phase of a GC cycle, the garbage collector will not scan the entries of the map.
This could save much time.</p>

<p>This tip is also valid for other kinds of container in Go, such as slices, arrays and channels.</p>

<h2>Using byte arrays instead of short strings as keys</h2>

<p>Internally, each string contains a pointer, which points to the underlying bytes of that string.
So if the key or element type of a map is a string type, then all the entries of the map
needs to be scanned in GC cycles.</p>

<p>If we can make sure that the string values used in the entries of a map have a max length
and the max length is small, then we could use the array type <code>[N]byte</code> to replace the string types
(where <code>N</code> is the max string length). Doing this will save much garbage collection scanning time
if the number of the entries in the map is very large.</p>

<p>For example, in the following code,
the entries of <code>mapB</code> contain no pointers, but the (string) keys of <code>mapA</code> contain pointers.
So garbage collector will skip <code>mapB</code> during the scan phase of a GC cycle.</p>

<pre><code class="language-Go">	var mapA = make(map[string]int, 1 &lt;&lt; 16)
	var mapB = make(map[[32]byte]int, 1 &lt;&lt; 16)
</code></pre>

<p>And please note that, the official standard compiler makes special optimizations
on hashing map keys whose sizes are 4 or 8 bytes.
So, from the point of view of saving CPU,
it is better to use <code>map[[8]byte]V</code> instead of <code>map[[5]byte]V</code>,
and it is better to use <code>map[int32]V</code> instead of <code>map[int16]V</code>.</p>

<h2>Lower map element modification frequency</h2>

<p>In the previous &quot;strings and byte slices&quot; chapter, it has been mentioned that
<a href="4-string-and-byte-slice.html#bytes-2-string-as-map-retrieval-key">a byte-slice-to-string conversion appearing as the index key in a map element retrieval expression
doesn't allocate</a>,
but such conversions in L-value map element index expressions will allocate.</p>

<p>So sometimes, we could lower the frequency of using such conversions in
L-value map element index expressions to improve program performance.</p>

<p>In the following example, the B way (pointer element way) is more performant than the A way.
The reason is the B way modifies element values rarely.
The elements in the B way are pointers, once they are created, they are never changed.</p>

<pre><code class="language-Go">package maps

import &quot;testing&quot;

var wordCounterA = make(map[string]int)
var wordCounterB = make(map[string]*int)
var key = make([]byte, 64)

func IncA(w []byte) {
	wordCounterA[string(w)]++
}

func IncB(w []byte) {
	p := wordCounterB[string(w)]
	if p == nil {
		p = new(int)
		wordCounterB[string(w)] = p
	}
	*p++
}

func Benchmark_A(b *testing.B) {
	for i := 0; i &lt; b.N; i++ {
		for i := range key {
			IncA(key[:i])
		}
	}
}

func Benchmark_B(b *testing.B) {
	for i := 0; i &lt; b.N; i++ {
		for i := range key {
			IncB(key[:i])
		}
	}
}
</code></pre>

<p>The benchmark results:</p>

<pre><code>Benchmark_A-4  11600 ns/op  2336 B/op  62 allocs/op
Benchmark_B-4   1543 ns/op     0 B/op   0 allocs/op
</code></pre>

<p>Although the B way (pointer element way) is less CPU consuming,
it creates many pointers, which increases the burden of pointer scanning in a GC cycle.
But generally, the B way is more efficient.</p>

<p>We could use an extra counter table (a slice) and let the map record indexes to the table,
to avoid making many allocations and creating many pointers, as the following code shows:</p>

<pre><code class="language-Go">var wordIndexes = make(map[string]int)
var wordCounters []int

func IncC(w []byte) {
	if i, ok := wordIndexes[string(w)]; ok {
		wordCounters[i]++
	} else {
		wordIndexes[string(w)] = len(wordCounters)
		wordCounters = append(wordCounters, 1)
	}
}

func Benchmark_C(b *testing.B) {
	for i := 0; i &lt; b.N; i++ {
		for i := range key {
			IncC(key[:i])
		}
	}
}
</code></pre>

<p>The benchmark results:</p>

<pre><code>Benchmark_A-4  11600 ns/op  2336 B/op  62 allocs/op
Benchmark_B-4   1543 ns/op     0 B/op   0 allocs/op
Benchmark_C-4   1609 ns/op     0 B/op   0 allocs/op
</code></pre>

<p>From a short-period view, the C way is as almost performant as the B way,
But as it uses much less pointers, it is actually more efficient than the B way in a long-period view.</p>

<p>Please note that the above benchmark results show the latter two ways both make zero allocations.
This is actually not true. It is just that each of latter two benchmark runs makes less than one allocation averagely, which is truncated to zero.
This is a <a href="https://github.com/golang/go/issues/24631">deliberate design</a> of the benchmark reports in the standard packages.</p>

<h2>Try to grow a map in one step</h2>

<p>If we could predict the max number of entries will be put into a map at coding time,
we should create the map with the <code>make</code> function and pass the max number as the <code>size</code> argument of the <code>make</code> call,
to avoid growing the map in multiple steps later.</p>

<h2>Use index tables instead of maps which key types have only a small set of possible values</h2>

<p>Some programmers like to use a map with bool key to reduce verbose <code>if-else</code> code block uses.
For example, the following code</p>

<pre><code class="language-Go">	// Within a function ...
	var condition bool
	condition = evaluateCondition()
	...
	if condition {
		counter++
	} else {
		counter--
	}
	...
	if condition {
		f()
	} else {
		g()
	}
	...
</code></pre>

<p>could be replaced with</p>

<pre><code class="language-Go">// Package-level maps.
var boolToInt = map[bool]int{true: 1, false: 0}
var boolToFunc = map[bool]func(){true: f, false: g}

	// Within a function ...
	var condition bool
	condition = evaluateCondition()
	...
	counter += boolToInt[condition]
	...
	boolToFunc[condition]()
	...
</code></pre>

<p>If there are many such identical <code>if-else</code> blocks used in code,
using maps with bool keys will reduce many boilerplates and make code look much cleaner.
For most use cases, this is generally good.
However, as of Go toolchain v1.24.n, <a href="https://github.com/golang/go/issues/44578">the map way is not very efficient from
the code execution performance view</a>.
The following benchmarks show the performance differences.</p>

<pre><code class="language-Go">package maps

import &quot;testing&quot;

//go:noiline
func f() {}

//go:noiline
func g() {}

func IfElse(x bool) func() {
	if x {
		return f
	} else {
		return g
	}
}

var m = map[bool]func() {true: f, false: g}
func MapSwitch(x bool) func() {
	return m[x]
}

func Benchmark_IfElse(b *testing.B) {
	for i := 0; i &lt; b.N; i++ {
		IfElse(true)()
		IfElse(false)()
	}
}

func Benchmark_MapSwitch(b *testing.B) {
	for i := 0; i &lt; b.N; i++ {
		MapSwitch(true)()
		MapSwitch(false)()
	}
}
</code></pre>

<p>The benchmark results:</p>

<pre><code>Benchmark_IfElse-4      4.155 ns/op
Benchmark_MapSwitch-4  47.46 ns/op
</code></pre>

<p>From the benchmark results, we could get that the <code>if-else</code>
block way is much more performant than the map-switch way.</p>

<p>For the use cases which require high code performance,
we can simulate a bool-key map by using an index table to reduce <code>if-else</code> boilerplates,
but still keep the simplicity of the map switch way,
with the help of a bool-to-int function.
The following benchmarks show how to use the index table way.</p>

<pre><code class="language-Go">func b2i(b bool) (r int) {
	if b {
		r = 1
	}
	return
}

var boolMap = [2]func(){g, f}

func Benchmark_BoolMap(b *testing.B) {
	for i := 0; i &lt; b.N; i++ {
		boolMap[b2i(true)]()
		boolMap[b2i(false)]()
	}
}
</code></pre>

<p>From the above code, we could find that the uses of the index table way are almost
as clean as the map-switch way, though an extra tiny <code>b2i</code> function is needed.
And from the following benchmark results, we know that the index table way
is as performant as the <code>if-else</code> block way.</p>

<pre><code>Benchmark_IfElse-4      4.155 ns/op
Benchmark_MapSwitch-4  47.46 ns/op
Benchmark_BoolMap-4     4.135 ns/op
</code></pre>
